package offer;

import java.util.LinkedList;
import java.util.Queue;

/*
* P55 面试题6：重建二叉树
* */
public class BuildBinaryTree {

    public static BinaryTreeNode buildTree(int[] preArr, int[] inArr) throws Exception {

        if(preArr == null || inArr == null || preArr.length != inArr.length){
            return null;
        }
        return build(preArr, inArr, 0, 0, preArr.length - 1);

    }

    private static BinaryTreeNode build(int[] preArr, int[] inArr, int index, int start, int end) throws Exception {

        BinaryTreeNode node = new BinaryTreeNode();
        node.value = preArr[index];
        if(start == end){
            if(preArr[index] != inArr[start]){
                throw new Exception("Invalid input");
            }
        } else {
            int i = start;
            for(; i <= end; i ++){
                if(inArr[i] == node.value){
                    break;
                }
            }
            if(inArr[i] != node.value){
                throw new Exception("Invalid input");
            }
            int leftLen = i - start;
            if(leftLen > 0){
                node.left = build(preArr, inArr, index + 1, start, i - 1);
            }
            if(i < end){
                node.right = build(preArr, inArr, index + leftLen + 1, i + 1, end);
            }
        }
        return node;
    }

    public static void printBTreeByLevel(BinaryTreeNode root){
        if(root == null){
            return;
        }
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        int curLevel = 0;
        queue.add(root);
        curLevel ++;
        int nextLevel = 0;
        while(!queue.isEmpty()){
            BinaryTreeNode node = queue.poll();
            if(node.left != null){
                queue.add(node.left);
                nextLevel ++;
            }
            if(node.right != null){
                queue.add(node.right);
                nextLevel ++;
            }
            System.out.print(node.value + " ");
            curLevel --;
            if(curLevel == 0){
                System.out.println();
                curLevel = nextLevel;
                nextLevel = 0;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BinaryTreeNode root = buildTree(new int[]{1,2,4,7,3,5,6,8}, new int[]{4,7,2,1,5,3,8,6});
        printBTreeByLevel(root);
    }
}
